#include "fun_trees.h"

/*
    ====================================================
                        平衡二叉树
    ====================================================
*/
/**
 * 功能：   比较节点的key值与key值的大小
 * 参数：   node 节点
 *         key  节点值
 * 返回值： -1  key值小于其节点的值，
 *          0  key值等于其节点的值，
 *          1  key值大于其节点的值，
 * 备注：   默认key是int*类型，若需要其他类型，则重写此函数
*/
int __weak fun_avl_compare(AVL_NODE *node, void *key)
{
    fun_avltree_unit *cp_node = (fun_avltree_unit *)node;
    int key_val = *(int*)key;
    int node_val = *(int*)cp_node->key;

    if (key_val < node_val) {
        return -1;
    }
    else if (key_val > node_val) {
        return 1;
    }
    else {
        return 0;
    }
}

/**
 * 功能：   平衡二叉树销毁回调函数
 * 参数：   pnode   当前被销毁的节点
 * 返回值： 0 成功 -1 立即停止销毁，并且avltree_destory返回-1；
 * 备注：   每个节点被销毁将调用此函数一次
*/
int __weak avltree_destory_callback(AVL_NODE *pNode)
{
    fun_avltree_unit *dl_node = (fun_avltree_unit*)pNode;
    dl_node->avl_node.height = 0;
    dl_node->avl_node.left = dl_node->avl_node.right = NULL;
    
    return 0;
}

/**
 * 功能：   将节点插入到树节点中
 * 参数：   root    树的根节点（其指向的内容会根据实际被修改）
 *         unit    插入的节点
 * 返回值： -1 失败 0 成功
 * 备注：   所有的节点跟内容都必须有实际的空间。避免使用局部变量。
*/
int avltree_insert(AVL_TREE *root, fun_avltree_unit *unit)
{
    return avl_insert(root, &unit->avl_node, unit->key, fun_avl_compare);
}

/**
 * 功能：   将节点从树中移除
 * 参数：   root    树的根节点（其指向的内容会根据实际被修改）
 *         key     删除的节点值
 * 返回值： 删除的节点
 * 备注：   删除只是在树上将对应的节点移除，但并不会对实际节点有影响
*/
fun_avltree_unit* avltree_delete(AVL_TREE *root, void *key)
{
    return (fun_avltree_unit*)avl_delete(root, key, fun_avl_compare);
}

/**
 * 功能：   从树中搜索节点值
 * 参数：   root    树的根节点
 *         key     搜索的节点值
 * 返回值： 指向节点的指针
 * 备注：  
*/
fun_avltree_unit *avltree_search(AVL_TREE *root,void *key)
{   
    return (fun_avltree_unit*)avl_search(*root,key,fun_avl_compare);
}

/**
 * 功能：   销毁平衡树
 * 参数：   root    平衡树的根节点
 * 返回值： -1 失败 0 成功
 * 备注：   成功后需要自行将root指向NULL
*/
int avltree_destory(AVL_TREE *root)
{
    return avl_destroy(*root,avltree_destory_callback);
}

/**
 * 打印二叉平衡树
*/
static void _avltree_print(AVL_TREE node,void *fkey, int direction)
{
    int key = *(int *)avl_entry(node,fun_avltree_unit,avl_node)->key;
    if(!direction)   //tree的根节点
    {
        printf("%2d is root,height is %d\n", key, avl_entry(node,fun_avltree_unit,avl_node)->avl_node.height);
    }
    else if(direction==-1)
    {
        printf("%2d is %2d's left  child,height is %d\n",
        *(int*)avl_entry(node,fun_avltree_unit,avl_node)->key,
        *(int*)fkey,
        avl_entry(node,fun_avltree_unit,avl_node)->avl_node.height);
    }
    else if(direction==1)
    {
        printf("%2d is %2d's right child,height is %d\n",
        *(int*)avl_entry(node,fun_avltree_unit,avl_node)->key,
        *(int*)fkey,
        avl_entry(node,fun_avltree_unit,avl_node)->avl_node.height);
    }
    
    if(avl_entry(node,fun_avltree_unit,avl_node)->avl_node.left)
    {
        _avltree_print(avl_entry(node,fun_avltree_unit,avl_node)->avl_node.left,
        avl_entry(node,fun_avltree_unit,avl_node)->key,
        -1);
    }
    if(avl_entry(node,fun_avltree_unit,avl_node)->avl_node.right)
    {
        _avltree_print(avl_entry(node,fun_avltree_unit,avl_node)->avl_node.right,
        avl_entry(node,fun_avltree_unit,avl_node)->key,
        1);
    }
}

/**
 * 功能：   打印平衡树
 * 参数：   root    树的根结点
 * 返回值：
 * 备注：   此函数仅限于打印key为int*类型的树，若需要打印其他，需要自行重写
*/
void __weak avltree_print(AVL_TREE root)
{
    if(root!=NULL)
        _avltree_print(root,NULL,0);
}

